Graphical networks

STK4141 - Probabilistic graphical models List of topics for the exam All the material that we have covered in class make up the topics for the exam, including the homework exercises. In terms of the course book, we have covered the following: Chapter 2 - Foundations All sections except 2.1.6. Chapter 3 - The Bayesian Network Representation All sections. Chapter 4 - Undirected Graphical Models All sections except 4.4.2 and 4.6. Chapter 9 - Exact Inference: Variable Elimination Only sections 9.2, 9.3, and 9.4.1-9.4.2. Chapter 10 - Exact Inference: Clique Trees All sections. Chapter 17 - Parameter Estimation All sections except 17.2.4, 17.5, and most of 17.6 (included from 17.6: 17.6.1 and 17.6.2.2 up til Lemma 17.2). Chapter 18 - Structure Learning in Bayesian Networks All sections except 18.4.4, 18.5, and 18.6. Chapter 20 - Learning Undirected Models All sections except 20.3.2-20.3.4, 20.4.2, 20.5, 20.6.2, and 20.7.4-20.7.5. Chapter 21 - Causality All sections except 21.4-21.6 and 21.7.4.

Graphoids & conditional independences

Bayesian networks

Conditioning

Mtd

Marginalization

Structure learning

Parameter estimation

Markov networks

Markov properties

Markov networks

Def

Independence maps

Separation

Def

Factorization

Independence by parameter

Factor graphs

Causality

Representing independences

The idea behind graphical models is to represent some of the independences of a distribution \(P\) as a graph.
(Note that we can use graphical models)

Graphoid

Symmetry

Weak union

Decomposition

Contraction

Intersection

DAG

Naive Bayes model

Conditioning a Bayesian network

Conditioning a Bayesian network on a set of variables \(Z\) delete some paths but might also introduce new paths.

d-separation

\(X\) and \(Y\) are d-separated given \(Z\) if there are no active paths between \(X\) and \(Y\) in the Bayesian network conditioned on \(Z.\)

Pairwise Markov property

Local Markov property

Global Markov property

Why Markov networks

Given a (possible large) set of variables, one may ask: which variables influence other variables, and which ignore each other? And: could we use this information to simplify the computations involving the distribution?
For a distribution \({P({\mathcal{X}}{})}\),
From the opposite perspective, we look for dependences instead of independences.
It turns out that given a set of independences,
If we choose to represent no indepdences,
Notice that when we do not consider any structural information at all, we do not have any independences; and we have all possible dependences between every node. As we add or obtain structural information, we add independences or equivalently remove possible dependences. So it is the independences that are considered "valuable"; they are what allows us to simplify the distribution, while dependences complicate it.
A Markov network lets us represent these independences using an undirected graph: nodes that are part of the same clique are considered to be dependent. So there is an equivalence between the independences/dependences,

Markov network

A Markov network (undirected graphical model) has an undirected graph with nodes \(I\) and a set of random variables \({X = {{{\left\{{X}_{i}\right\}}}}_{{i \in{} I}}}\) that satisfies the global Markov property.
So a Markov network is a distribution \(P\) and a choice of factorization or choice of independences of \(P\) represented by an undirected graph.

Structure of a Markov network

Distribution of a Markov network

Gibbs distribution

A Gibbs distribution is

Pairwise Markov network

In a pairwise Markov network, there are additional constraints on allowed factors. This however is very fine grained.

Independence map

An independence map (I-map) of \(P\) represents independences between variables of \(P\). If there is no edge between \(X\) and \(Y,\) then they are conditionally independent.
From the opposite perspective, an independence map represents potential dependences between variables. If there is an edge between \(X\) and \(Y,\) they may be dependent.

Trivial imap

Let \({\mathcal{H}}\) be a perfect graph over \({\mathcal{X}}\). This Markov network does not represent any indepdences at all.

Minimal independence map

The minimal independence map over \(P\)

Trivial Markov network

The trivial Markov network is the one with the trivial independence map over \(P\); it does not encode any potential independences – every variable is potentially dependent.

Hammersley–Clifford theorem

If the undirected graph \({\mathcal{H}}\) is an independence map for positive \(P\), then \(P\) is a Gibbs distribution that factorizes over \({\mathcal{H}}\).
(If \({\mathcal{H}}\) encodes independences between variables that are actually dependent in \(P\), \(P\) does not factorize according to \({\mathcal{H}}\).)

Markov network conditioned on \(Z\)

Separation

Definition

Let \({\mathbf{D}}\) be a set of random variables. A factor is a function \({{\mathbf{D}} \to{} {\mathbb{R}}}\).
A factor quantifies the affinity between the values of \({\mathbf{D}}\): high affinity means that the values are compatible and likely to ocurr together.

Factor of a Gibbs distribution

Scope of a factor

Gibbs distribution factorizing over \(\mathcal{H}\)

A Gibbs distribution \({P}_{\Phi}\) factorizes over a Markov network \({\mathcal{H}}\) if each \({\mathbf{D_k}}\) is a complete subgraph of \({\mathcal{H}}\).

Reduction of a factor

Gibbs distribution reduced by \(u\)

Markov network reduced by \(u\)

Let

Soundness & completeness

For Markov networks, we want to make sure, in a parallel to logic, that if \(X\) and \(Y\) are conditionally independent, then they are separated in the network structure.

Soundness

If an I-map encodes an independence of \(X\) and \(Y\), then \(X\) and \(Y\) are independent given \(Z\).

Clique factorization of a Markov network

A factor in the factor parametrization of H is known as a clique potential, and the set of variables a clique.

Clique

Clique potential

Granularity of parametrization

The finest parametrization is based on having one factor per edge.
The coarsest parametrization is based on having one factor per clique.

Independence by parameter

Given a distribution \({P{{\left[{X \vert{} \Theta}\right]}}}\), the minimal independence map can be constructed. We could think that these are all the independences; however, more independences might arise because of the parameters \(\theta\) themselves.

Factor graph

Log-linear representation of a Markov network

A Markov network with positive factors can be represented by a log-linear formula. \(X\)